#include "BinaryTree.h"
#include "stack.h"
////////////打印
void PrintArray(int* a,int n)
{
    for (int i = 0; i < n; ++i)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
}
void Swap(int*x,int*y)
{
    int tmp = *x;
    *x = *y;
    *y = tmp;
}
///////冒泡排序
void BubbleSort(int* a,int n)
{
    for (int i = 1; i < n; ++i)
    {
        int count = 0;
        for (int j = 0; j < n-i; ++j)
        {
            if(a[j] > a[j+1])
            {
                count = 1;
                Swap(&a[j],&a[j+1]);
            }
        }
        if(count == 0)
            break;
    }
}
///////堆排序,升序，建大堆
void AdjustDown(int* a,int parent,int n)
{
    int child = parent*2 + 1;
    while(child < n)
    {
        if(child + 1 < n && a[child] < a[child+1])
        {
            child = child + 1;
        }
        if(a[parent] < a[child])
        {
            Swap(&a[parent],&a[child]);
            parent = child;
            child = parent*2 + 1;
        }
        else
            break;
    }
}
void HeapSort(int* a,int n)
{
    int child = n-1;
    int parent = (child-1)/2;

    while (parent >= 0)
    {
        AdjustDown(a,parent,n);
        parent--;
    }

    int end = n-1;
    while (end)
    {
        Swap(&a[0],&a[end]);
        AdjustDown(a,0,end);
        end--;
    }
}
//////////插入排序
void InsertSort(int* a,int n)
{
    for(int i = 0; i < n-1; i++)
    {
        int end = i;
        int tmp = a[end+1];
        while(end >= 0)
        {
            if(a[end] > tmp)
            {
                a[end+1] = a[end];
                end--;
            }
            else
                break;
        }
        a[end+1] = tmp;
    }
}
/////////选择排序
void SelectSort(int* a,int n)
{
    int begin = 0;
    int end = n-1;

    while (begin < end)
    {
        int maxi = begin;
        int mini = begin;
        for (int i = begin+1; i <= end; ++i)
        {
            if(a[mini] > a[i])
            {
                mini = i;
            }
            if(a[maxi] < a[i])
            {
                maxi = i;
            }
        }
        Swap(&a[begin],&a[mini]);
        if(maxi == begin)
            maxi = mini;

        Swap(&a[end],&a[maxi]);

        begin++;
        end--;
    }
}
//////////希尔排序
void ShellSort(int* a,int n)
{
    int gap = n;
    while(gap > 1)
    {
        gap = gap / 2;
        for (int i = 0; i < n-gap; ++i)
        {
            int end = i;
            int tmp = a[end+gap];
            while(end >= 0)
            {
                if(a[end] > tmp)
                {
                    a[end+gap] = a[end];
                    end = end - gap;
                }
                else
                    break;
            }
            a[end+gap] = tmp;
        }
    }
}
////三值取中
int GetMidi(int* a,int left,int right)
{
    int mid = (left + right) / 2;
    if(a[left] < a[mid])
        Swap(&left,&mid);
    if(a[left] < a[right])
        Swap(&left,&right);
    if(a[mid] < a[right])
        Swap(&mid,&right);
    return mid;
}

////////////快速排序hoare
void QuickSort1(int* a,int left,int right)
{
    int begin = left;
    int end = right;
/////////小于10之后，就不用递归了，直接插入排序就OK，要不然递归太深会爆栈
    if(right-left+1 <= 10)
    {
        InsertSort(a+left,right-left+1);
        return;
    }
    else
    {
        int mid = GetMidi(a,left,right);
        Swap(&a[mid],&a[left]);

        int key  = left;

        while(left < right)
        {
            while(left < right && a[right] >= a[key])
            {
                right--;
            }
            while(left < right && a[left] <= a[key])
            {
                left++;
            }
            Swap(&a[left],&a[right]);

        }
        Swap(&a[left],&a[key]);
    }

    QuickSort1(a,begin,left-1);
    QuickSort1(a,left+1,end);
}
///////////快速排序挖坑法
void QuickSort2(int* a,int left,int right)
{
    if(left >= right)
        return;

    int begin = left;
    int end = right;

    int mid = GetMidi(a,left,right);
    Swap(&a[mid],&a[left]);

    int key  = a[left];
    int hole = left;

    while (left < right)
    {
        while(left < right && a[right] >= key)
        {
            right--;
        }
        a[hole] = a[right];
        hole = right;
        while(left < right && a[left] <= key)
        {
            left++;
        }
        a[hole] = a[left];
        hole = left;
    }
    a[hole] = key;

    QuickSort2(a,begin,hole-1);
    QuickSort2(a,hole+1,end);
}
///////////////快速排序前后指针法
void QuickSort3(int* a,int left,int right)
{
    if(left >= right)
        return;
    int begin = left;
    int end = right;

    int mid = GetMidi(a,left,right);
    Swap(&a[mid],&a[left]);

    int key  = left;
    int prev = left;
    int cur = prev + 1;

    while (cur <= right)
    {
        if(a[cur] < a[key] && prev++ != cur)
        {
            Swap(&a[prev],&a[cur]);
        }
        cur++;
    }
    Swap(&a[key],&a[prev]);

    QuickSort3(a,begin,prev-1);
    QuickSort3(a,prev+1,end);

}
/////////////////////归并排序递归实现
void recursion(int* a,int* tmp,int left,int right)
{
    if(left >= right)
        return;
    int mid = (left+right) / 2;
    recursion(a,tmp,left,mid);
    recursion(a,tmp,mid+1,right);

    int begin1 = left;
    int end1 = mid;
    int begin2 = mid + 1;
    int end2 = right;

    int k = left;
    while(begin1 <= end1 && begin2 <= end2)
    {
        if(a[begin1] < a[begin2])
        {
            tmp[k++] = a[begin1++];
        }
        else
        {
            tmp[k++] = a[begin2++];
        }
    }
    while(begin1 <= end1)
    {
        tmp[k++] = a[begin1++];
    }
    while (begin2 <= end2)
    {
        tmp[k++] = a[begin2++];
    }

    memcpy(a+left,tmp+left,sizeof (int)*(right-left+1));
}
void MergeSort(int* a,int n)
{
    int* tmp = (int*) malloc(sizeof(int)*n);
    if(tmp == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    recursion(a,tmp,0,n-1);
    free(tmp);
}
////////////归并排序（Not Recursion）
void MergeSortNotR(int* a,int n)
{
    int* tmp = (int*) malloc(sizeof(int)*n);
    if(tmp == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    int gap = 1;
    while(gap < n)
    {
        for (int i = 0; i < n; i = i + gap*2)
        {
            int begin1 = i;
            int end1 = begin1 + gap - 1;
            int begin2 = end1 + 1;
            int end2 = begin2 + gap - 1;

           // 第二组不存在
            if(begin2 >= n)
                break;
            //第二组右边界越界
            if(end2 >= n)
                end2 = n - 1;

            int k = i;
            while(begin1 <= end1 && begin2 <= end2)
            {
                if(a[begin1] < a[begin2])
                {
                    tmp[k++] = a[begin1++];
                }
                else
                {
                    tmp[k++] = a[begin2++];
                }
            }
            while(begin1 <= end1)
            {
                tmp[k++] = a[begin1++];
            }
            while (begin2 <= end2)
            {
                tmp[k++] = a[begin2++];
            }

            memcpy(a+i,tmp+i,sizeof (int)*(end2-i+1));
        }
        gap = gap * 2;
    }
    free(tmp);
}
///////计数排序(只适合非负整数排序)
void CountSort(int* a,int n)
{
    int min = a[0];
    int max = a[0];
    for (int i = 0; i < n; ++i)
    {
        if(min > a[i])
            min = a[i];
        if(max < a[i])
            max = a[i];
    }

    int* arr = (int*) malloc(sizeof (int)*(max-min+1));

    if(arr == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }

    for (int i = 0; i < max-min+1; ++i)
    {
        arr[i] = 0;
    }

    for (int i = 0; i < n; ++i)
    {
        arr[a[i] - min]++;
    }

    int j = 0;
    for(int i = 0; i < max-min+1; i++)
    {
        while(arr[i]--)
        {
            a[j++] = i + min;
        }
    }

}
